/*
 * Dan Jaglowski
 * CIS 452 - Fall 2011
 * Project 1 - Multi-Process External Sort
 *
 * This program sorts a distributed set of integers. 
 */
#include <stdio.h>
#include <stdlib.h>
#include <signal.h>
#include <unistd.h>
#include <string.h>
#include <fcntl.h>
#include <sys/wait.h>

#define READ 0
#define WRITE 1
#define LEFT 0
#define RIGHT 1
#define NUM_FILES 4
#define NUMS_PER_FILE 4

// These are the pid's of the process's children
pid_t leftPid, rightPid;

// For writing to the parent
int upPipe[2];

// For reading from children
int leftPipe[2], rightPipe[2];

// These indices represent a range of files which may be read
// As processes are spawned, the range is narrowed
// Leaf processes have the same value for both indices
int minIndex = 0;
int maxIndex = NUM_FILES - 1;

// Primary control function
void breed();

// Secondary control functions
void doParent();
void doLeaf();

// Setup functions
void createPipes();
void setupChild(int);

// Helper functions
void merge();
void writeUp(int);
int intcmp(const void *n1, const void *n2);

/*
 * The main function begins program execution.
 */
int main()
{
	createPipes();

  	breed();

	return 0;
}

/*
 * This is a helper function which initializes the three pipes.
 * 
 * It also closes the read end of the upPipe, because it is not
 * used by any of the processes.
 */
void createPipes()
{
	// Create all three pipes
	if(pipe(upPipe) < 0 || pipe(leftPipe) < 0 || pipe(rightPipe) < 0)
	{
		// There was a problem
		perror("\nFailed to create upPipe");
	}

	// Success
	else	
	{
		// Close the read end of upPipe. It's never used
		close(upPipe[READ]);
	}
}

/*
 * This is a recursive function which forks off two child processes.
 * 
 * It then passes control of each process to the appropriate handler.
 *
 * There is some repeated code, but this prevents unneeded function stacking.
 */
void breed()
{
    // Spawn the left child
    if((leftPid = fork()) < 0)
	{
		// There was an error
        perror("\nFailed to fork");
	}

	// Check if this is the left child
    else if(leftPid == 0)
    {
		fprintf(stderr, "\nProcess %d: Created", getpid());
		sleep(1);

		// It is. Setup pipes, indices, ect
		setupChild(LEFT);

		// Check if this is a leaf process
		if(minIndex == maxIndex)
		{
			// It is. Pass control to leaf handler
			doLeaf();
		}

		// This is an internal process
		else
		{
			// Continue spawning children			
			breed();
		}
    }

	// Spawn the right child
    else if((rightPid = fork()) < 0)
	{
		// There was an error
	    perror("\nFailed to fork");
	}

	// Check if this is the right child
	else if(rightPid == 0)
	{	
		fprintf(stderr, "\nProcess %d: Created", getpid());
		sleep(1);		

		// It is. Setup pipes, indices, ect
		setupChild(RIGHT);

		// Check if this is a leaf process
		if(minIndex == maxIndex)
		{
			// This is a leaf node
			doLeaf();
		}

		// This is an internal process
		else
		{
			// Continue spawning children			
			breed();
		}
	}

	// This is the parent
	else
	{
		// Handle parent
		doParent();
	}
}

/*
 * This function sets up four minor aspects of each child process.
 * 
 * 1. Clears the master flag
 * 2. Redirects output to the correct pipe
 * 3. Creates new left and right pipes
 * 4. Constrains the file indices
 */
void setupChild(int side)
{
	// Determine which side the child is on
	if(side == LEFT)
	{
		// The leftPipe is our connection to the parent, redirect it to upPipe
		dup2(leftPipe[WRITE], upPipe[WRITE]);
	}
	else	
	{
		// The rightPipe is our connection to the parent, redirect it to upPipe
		dup2(rightPipe[WRITE], upPipe[WRITE]);
	}

	// Create new lower pipes
	if(pipe(leftPipe) < 0 || pipe(rightPipe) < 0)
	{
		// There was a problem
		perror("\nFailed to create pipes");
	}

	// Check which side again
	if(side == LEFT)
	{
		// Bring down the max index by half the range
		maxIndex = minIndex + ((maxIndex - minIndex) - 1) / 2;
	}	
	else
	{	
		// Bring up the min index by half the range
		minIndex = minIndex + ((maxIndex - minIndex) + 1) / 2;
	}
}

/*
 * This is the main handler for all parent processes.
 * 
 * Each process merges its childrens' results and passes them along.
 */
void doParent()
{
	int leftStatus, rightStatus;

	// Check if this is the master process
	if((maxIndex - minIndex) == (NUM_FILES - 1))
	{
		// Redirect the upPipe to stdout
		dup2(STDOUT_FILENO, upPipe[WRITE]);
	}

	// The write ends of the lower pipes belong to children only
	close(leftPipe[WRITE]);
	close(rightPipe[WRITE]);

	// Wait for both children to finish
	waitpid(leftPid, &leftStatus, 0);
	waitpid(rightPid, &rightStatus, 0);

	fprintf(stderr, "\nProcess %d: Children Done", getpid());
	sleep(1);

	merge();

	// Close remaining pipes
	close(upPipe[WRITE]);
	close(leftPipe[READ]);
	close(rightPipe[READ]);

	fprintf(stderr, "\nProcess %d: Done", getpid());
	sleep(1);
}

/*
 * This is the main handler for terminal (leaf) processes.
 * 
 * Each leaf reads numbers from a file, sorts them, and passes them along.
 */
void doLeaf()
{
	int i;	
	int numbers[NUMS_PER_FILE];
	char filename[10];
	FILE *file;

	// Close the lower pipes entirely
	close(leftPipe[READ]);
	close(leftPipe[WRITE]);
	close(rightPipe[READ]);
	close(rightPipe[WRITE]);

	// Use the index to generate the input file name
	sprintf(filename, "%d.txt", minIndex);

	// Open the input file
	file = fopen(filename, "r");

	fprintf(stderr, "\nProcess %d: Reading from %s", getpid(), filename);
	sleep(1);

	// Scan in all the numbers
	for(i = 0; i < NUMS_PER_FILE; i++)
	{
		// Get the next number
		fscanf(file, "%d", &numbers[i]);
	}

	fprintf(stderr, "\nProcess %d: Read %d Integers", getpid(), i);
	sleep(1);

	// Done with the file. Close it
	fclose(file);

	fprintf(stderr, "\nProcess %d: Beginning to Sort", getpid());
	sleep(1);

	// Sort the numbers
	qsort(numbers, NUMS_PER_FILE, sizeof(int), intcmp);

	fprintf(stderr, "\nProcess %d: Done Sorting", getpid());
	sleep(1);

	// Push the numbers up
	for(i = 0; i < NUMS_PER_FILE; i++)
	{
		// Push up the next number
		writeUp(numbers[i]);
	}

	// Done. Close remaining pipe
	close(upPipe[WRITE]);

	fprintf(stderr, "\nProcess %d: Done", getpid());
	sleep(1);
}


void merge()
{
	int leftNum, rightNum;
	int leftExists, rightExists;

	// Get the initial values from each child
	leftExists = read(leftPipe[READ], &leftNum, sizeof(int));
	rightExists = read(rightPipe[READ], &rightNum, sizeof(int));

	// Scan in all values from children
	while (leftExists || rightExists)
	{	
		// Check if the left pipe is empty
		if(!leftExists)
		{
			fprintf(stderr, "\nProcess %d: Left Pipe Empty", getpid());
			sleep(1);

			// Push up the rest of rightPipe
			while(rightExists)
			{
				// Put the existing value in the upPipe
				writeUp(rightNum);			

				// Get the next value
				rightExists = read(rightPipe[READ], &rightNum, sizeof(int));
			}

			fprintf(stderr, "\nProcess %d: Right Pipe Empty", getpid());
			sleep(1);
		}

		// Check if the right pipe is empty
		else if(!rightExists)
		{
			fprintf(stderr, "\nProcess %d: Right Pipe Empty", getpid());
			sleep(1);

			// Push up the rest of leftPipe
			while(leftExists)
			{
				// Put the existing value in the upPipe
				writeUp(leftNum);

				// Get the next value
				leftExists = read(leftPipe[READ], &leftNum, sizeof(int));
			}

			fprintf(stderr, "\nProcess %d: Left Pipe Empty", getpid());
			sleep(1);
		}

		// Compare the values
		else if(leftNum < rightNum)
		{
			// The leftNum is smaller. Push it up
			writeUp(leftNum);

			// Get the next value
			leftExists = read(leftPipe[READ], &leftNum, sizeof(int));

		}
		else
		{
			// The rightNum is smaller or equal. Push it up
			writeUp(rightNum);

			// Get the next value
			rightExists = read(rightPipe[READ], &rightNum, sizeof(int));
		}
	}
}

/*
 * This is a helper function for writing to the upPipe
 * The master process must format it's output before pushing up
 */
void writeUp(int number)
{
	// Check if this is the master process
	if((maxIndex - minIndex) == (NUM_FILES - 1))
	{
		// It is. Format output for stdout
		char str[15];
		sprintf(str, "Master: %5d\n", number);
		sleep(1);

		// Write the number to stdout
		write(upPipe[WRITE], str, sizeof(str));
	}

	// This is a normal process
	else
	{
		fprintf(stderr, "\nProcess %d: Writing %d", getpid(), number);
		sleep(1);

		// Push the number up
		write(upPipe[WRITE], &number, sizeof(int));
	}
}

/*
 * This is a auxillary function for comparing two integers
 * Return values:
 *		-1 if the first integer is less than the second
 * 		 0 if the integers are equal
 * 		 1 if the first integer is greater than the second 
 */
int intcmp(const void *n1, const void *n2)
{
	const int *num1 = (const int *)n1;
	const int *num2 = (const int *)n2;
	return (*num1 < *num2) ? -1 : (*num1 > *num2);
}
